home *** CD-ROM | disk | FTP | other *** search
/ Gekkan Dennou Club 145 / Gekkan Dennou Club - 2000.6 Vol. 145 (Japan) (Track 1).bin / docs / perl / bintree.pm < prev    next >
Encoding:
Perl POD Document  |  2000-04-22  |  1.5 KB  |  78 lines
  1. #
  2. # Bintree.pm : 二分探索木（オブジェクトのテスト）
  3. #
  4. # 格納するデータはオブジェクトであること
  5. #
  6. package Bintree;
  7.  
  8. # 終端を示す nil 用無名空ハッシュ
  9. $nil = {};
  10. bless $nil, 'Bintree';
  11.  
  12. # 二分木を空に初期化
  13. sub make_tree { $nil; }
  14.  
  15. # 二分木の探索
  16. sub search_tree {
  17.   my ($node, $item) = @_;
  18.   while( $node != $nil ){
  19.     my $result = $item->compare( $node->{'item'} );
  20.     if( $result == 0 ){
  21.       return 1;
  22.     } elsif( $result < 0 ){
  23.       $node = $node->{'left'};
  24.     } else {
  25.       $node = $node->{'right'};
  26.     }
  27.   }
  28.   0;
  29. }
  30.   
  31. # データの追加
  32. sub insert_tree {
  33.   my ($node, $item) = @_;
  34.   if( $node == $nil ){
  35.     my $new = {'item' => $item, 'left' => $nil, 'right' => $nil };
  36.     bless $new, 'Bintree';
  37.     return $new;
  38.   } else {
  39.     my $result = $item->compare( $node->{'item'} );
  40.     if( $result < 0 ){
  41.       $node->{'left'} = &insert_tree( $node->{'left'}, $item );
  42.     } elsif( $result > 0 ){
  43.       $node->{'right'} = &insert_tree( $node->{'right'}, $item );
  44.     }
  45.   }
  46.   $node;
  47. }
  48.  
  49. # 二分木の表示
  50. sub print_tree {
  51.   my $node = shift;
  52.   if( $node != $nil ){
  53.     &print_tree( $node->{'left'} );
  54.     $node->{'item'}->print_object();
  55.     &print_tree( $node->{'right'} );
  56.   }
  57. }
  58.  
  59. # debug print
  60. sub print_tree_test {
  61.   my ($node, $level) = @_;
  62.   my $i;
  63.   if( $node != $nil ){
  64.     &print_tree_test( $node->{'left'}, $level + 1 );
  65.     for( $i = 0; $i < $level; $i++ ){
  66.       print "  ";
  67.     }
  68.     $node->{'item'}->print_object();
  69.     &print_tree_test( $node->{'right'}, $level + 1 );
  70.   }
  71. }
  72.  
  73.  
  74. 1;
  75.  
  76. # end of file
  77.  
  78.